{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "fd920542",
   "metadata": {},
   "source": [
    "# 算法精粹：经典计算机科学问题的 Python 实现\n",
    "\n",
    "## 第一章 几个小问题"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d1bf6a0a",
   "metadata": {},
   "source": [
    "### 1.1 斐波那契序列\n",
    "**斐波那契序列**（Fibonacci sequence）是一系列数字，其中除第1个和第2个数字之外，其他数字都是前两个数字之和：\n",
    "\n",
    "$$0, 1, 1, 2, 3, 5, 8, 13, 21, …$$\n",
    "\n",
    "在此序列中，第1个斐波那契数是0。第4个斐波那契数是2。后续任一斐波那契数n的值可用以下公式求得：\n",
    "\n",
    "$$fib(n) = fib(n − 1) + fib(n − 2)$$\n",
    "\n",
    "> 由于Jupyter无法捕捉**RecursionError**: maximum recursion depth exceeded(递归调用超出限制错误)\n",
    "> \n",
    "> 会造成kernel挂掉重启, 下面第一种递归调用代码请复制到本地IDE环境执行\n",
    "\n",
    "``` python\n",
    "def fib1(n: int) -> int:\n",
    "    return fib1(n - 1) + fib1(n - 2)\n",
    "```\n",
    "\n",
    "执行结果会报错：`RecursionError: maximum recursion depth exceeded`\n",
    "\n",
    "**解释**：函数未设置下限，造成无限递归调用。\n",
    "\n",
    "参考[Stackoverflow](https://stackoverflow.com/questions/3323001/what-is-the-maximum-recursion-depth-in-python-and-how-to-increase-it)，可以手动调节recursion depth： `sys.setrecursionlimit(3600)`\n",
    "\n",
    "下面有关递归**调用次数**的[推导](https://blog.csdn.net/qq_43411555/article/details/88400990), [代码](https://blog.csdn.net/qq_46049116/article/details/103630603)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "id": "f27568d0",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 ---->耗时: 0.000003s 计算fab(2)调用3次\n",
      "2 ---->耗时: 0.000005s 计算fab(3)调用5次\n",
      "3 ---->耗时: 0.000005s 计算fab(4)调用9次\n",
      "5 ---->耗时: 0.000006s 计算fab(5)调用15次\n",
      "8 ---->耗时: 0.000009s 计算fab(6)调用25次\n",
      "13 ---->耗时: 0.000015s 计算fab(7)调用41次\n",
      "21 ---->耗时: 0.000023s 计算fab(8)调用67次\n",
      "34 ---->耗时: 0.000037s 计算fab(9)调用109次\n",
      "55 ---->耗时: 0.000060s 计算fab(10)调用177次\n",
      "89 ---->耗时: 0.000097s 计算fab(11)调用287次\n",
      "144 ---->耗时: 0.000157s 计算fab(12)调用465次\n",
      "233 ---->耗时: 0.000293s 计算fab(13)调用753次\n",
      "377 ---->耗时: 0.000417s 计算fab(14)调用1219次\n",
      "610 ---->耗时: 0.000714s 计算fab(15)调用1973次\n",
      "987 ---->耗时: 0.001119s 计算fab(16)调用3193次\n",
      "1597 ---->耗时: 0.002088s 计算fab(17)调用5167次\n",
      "2584 ---->耗时: 0.003337s 计算fab(18)调用8361次\n",
      "4181 ---->耗时: 0.006361s 计算fab(19)调用13529次\n",
      "6765 ---->耗时: 0.007771s 计算fab(20)调用21891次\n",
      "10946 ---->耗时: 0.018308s 计算fab(21)调用35421次\n",
      "17711 ---->耗时: 0.019255s 计算fab(22)调用57313次\n",
      "28657 ---->耗时: 0.030712s 计算fab(23)调用92735次\n",
      "46368 ---->耗时: 0.050106s 计算fab(24)调用150049次\n",
      "75025 ---->耗时: 0.078581s 计算fab(25)调用242785次\n",
      "121393 ---->耗时: 0.133462s 计算fab(26)调用392835次\n",
      "196418 ---->耗时: 0.208517s 计算fab(27)调用635621次\n",
      "317811 ---->耗时: 0.349321s 计算fab(28)调用1028457次\n",
      "514229 ---->耗时: 0.594297s 计算fab(29)调用1664079次\n",
      "832040 ---->耗时: 0.844773s 计算fab(30)调用2692537次\n"
     ]
    }
   ],
   "source": [
    "from time import perf_counter as tic\n",
    "def fib2(n: int) -> int:\n",
    "    global count\n",
    "    if n < 2:\n",
    "        count=count + 2\n",
    "        return n\n",
    "    return fib2(n - 1) + fib2(n - 2)\n",
    "\n",
    "for i in range(2,31):\n",
    "    count = -1\n",
    "    st = tic()\n",
    "    print(fib2(i),\"---->耗时: {:5f}s\".format(tic() - st), f\"计算fab({i})调用{count}次\")\n",
    "\n",
    "# n大于30就容易挂掉, 需做如下改动\n",
    "#from sys import setrecursionlimit\n",
    "#setrecursionlimit(9000)\n",
    "#st = tic()\n",
    "#print(fib2(40),\"---->耗时: {}s\".format(tic() - st))\n",
    "#setrecursionlimit(1000) # 还原默认值：1000"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "id": "0e829569",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "102334155 ---->耗时: 0.000270s ---->字典长度：41\n"
     ]
    }
   ],
   "source": [
    "from time import perf_counter as tic\n",
    "from typing import Dict\n",
    "# 字典缓存\n",
    "memo: Dict[int, int] = {0: 0, 1: 1}\n",
    "\n",
    "def fib3(n: int) -> int:\n",
    "    if n not in memo: \n",
    "        memo[n] = fib3(n - 1) + fib3(n - 2)\n",
    "    return memo[n]\n",
    "\n",
    "st = tic()\n",
    "print(fib3(40),\"---->耗时: {:5f}s\".format(tic() - st),f\"---->字典长度：{len(memo)}\")\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "id": "86f32b7e",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "12586269025 ---->耗时: 0.000226s\n"
     ]
    }
   ],
   "source": [
    "from time import perf_counter as tic\n",
    "from functools import lru_cache\n",
    "\n",
    "#python内置自动缓存装饰器\n",
    "@lru_cache(maxsize=None)\n",
    "def fib4(n: int) -> int:  # same definition as fib2()\n",
    "    if n < 2:  # base case\n",
    "        return n\n",
    "    return fib4(n - 2) + fib4(n - 1)  # recursive case\n",
    "\n",
    "st = tic()\n",
    "print(fib4(50),\"---->耗时: {:5f}s\".format(tic() - st))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "id": "018b5c19",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "12586269025 ---->耗时: 0.000113s\n"
     ]
    }
   ],
   "source": [
    "from time import perf_counter as tic\n",
    "#迭代法\n",
    "def fib5(n: int) -> int:\n",
    "    if n == 0: return n  # special case\n",
    "    last: int = 0  # fib(0)\n",
    "    next: int = 1  # fib(1)\n",
    "    for _ in range(1, n):\n",
    "        last, next = next, last + next\n",
    "    return next\n",
    "st=tic()\n",
    "print(fib5(50),\"---->耗时: {:5f}s\".format(tic() - st))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6f7091bf",
   "metadata": {},
   "source": [
    "### 1.2 简单的压缩\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "id": "3dbb8a71",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "original is 8649 bytes\n",
      "compressed is 2320 bytes\n",
      "TAGGGATTAACCGTTATATATATATAGCCATGGATCGATTATATAGGGATTAACCGTTATATATATATAGCCATGGATCGATTATATAGG\n",
      "original and decompressed are the same: True\n"
     ]
    }
   ],
   "source": [
    "class CompressedGene:\n",
    "    def __init__(self, gene: str) -> None:\n",
    "        self._compress(gene)\n",
    "        \n",
    "    def _compress(self, gene: str) -> None:\n",
    "        self.bit_string: int = 1  # start with sentinel\n",
    "        for nucleotide in gene.upper():\n",
    "            self.bit_string <<= 2  # shift left two bits\n",
    "            if nucleotide == \"A\":  # change last two bits to 00\n",
    "                self.bit_string |= 0b00\n",
    "            elif nucleotide == \"C\":  # change last two bits to 01\n",
    "                self.bit_string |= 0b01\n",
    "            elif nucleotide == \"G\":  # change last two bits to 10\n",
    "                self.bit_string |= 0b10\n",
    "            elif nucleotide == \"T\":  # change last two bits to 11\n",
    "                self.bit_string |= 0b11\n",
    "            else:\n",
    "                raise ValueError(\"Invalid Nucleotide:{}\".format(nucleotide))\n",
    "            \n",
    "    def decompress(self) -> str:\n",
    "        gene: str = \"\"\n",
    "        for i in range(0, self.bit_string.bit_length() - 1, 2):  # -1 to exclude sentinel\n",
    "            bits: int = self.bit_string >> i & 0b11  # get just 2 relevant bits\n",
    "            if bits == 0b00:  # A\n",
    "                gene += \"A\"\n",
    "            elif bits == 0b01:  # C\n",
    "                gene += \"C\"\n",
    "            elif bits == 0b10:  # G\n",
    "                gene += \"G\"\n",
    "            elif bits == 0b11:  # T\n",
    "                gene += \"T\"\n",
    "            else:\n",
    "                 raise ValueError(\"Invalid bits:{}\".format(bits))\n",
    "        return gene[::-1]  # [::-1] reverses string by slicing backward\n",
    "    def __str__(self) -> str:  # string representation for pretty printing\n",
    "        return self.decompress()\n",
    "\n",
    "from sys import getsizeof\n",
    "original: str = \"TAGGGATTAACCGTTATATATATATAGCCATGGATCGATTATATAGGGATTAACCGTTATATATATATAGCCATGGATCGATTATA\" * 100\n",
    "print(f\"original is {getsizeof(original)} bytes\")\n",
    "compressed: CompressedGene = CompressedGene(original)  # compress\n",
    "print(f\"compressed is {getsizeof(compressed.bit_string)} bytes\")\n",
    "print(str(compressed)[:90])  # decompress\n",
    "print(\"original and decompressed are the same: {}\".format(original == compressed.decompress()))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d2a95bdc",
   "metadata": {},
   "source": [
    "### 1.3 牢不可破的加密"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "id": "6951e156",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "One Time Pad!\n"
     ]
    }
   ],
   "source": [
    "from secrets import token_bytes\n",
    "from typing import Tuple\n",
    "\n",
    "def random_key(length: int) -> int:\n",
    "    # generate length random bytes\n",
    "    tb: bytes = token_bytes(length)\n",
    "    # convert those bytes into a bit string and return it\n",
    "    return int.from_bytes(tb, \"big\")\n",
    "\n",
    "def encrypt(original: str) -> Tuple[int, int]:\n",
    "    original_bytes: bytes = original.encode()\n",
    "    dummy: int = random_key(len(original_bytes))\n",
    "    original_key: int = int.from_bytes(original_bytes, \"big\")\n",
    "    encrypted: int = original_key ^ dummy  # XOR\n",
    "    return dummy, encrypted\n",
    "\n",
    "def decrypt(key1: int, key2: int) -> str:\n",
    "    decrypted: int = key1 ^ key2  # XOR\n",
    "    temp: bytes = decrypted.to_bytes((decrypted.bit_length()+ 7) // 8, \"big\")\n",
    "    return temp.decode()\n",
    "\n",
    "key1, key2 = encrypt(\"One Time Pad!\")\n",
    "result: str = decrypt(key1, key2)\n",
    "print(result)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7216b928",
   "metadata": {},
   "source": [
    "### 1.4 计算$\\pi$\n",
    "\n",
    "数学意义重大的$\\pi$（3.14159…）用很多公式都可以推导出来，其中最简单的公式之一就是莱布尼茨公式。它断定以下无穷级数的收敛值等于$\\pi$：\n",
    "\n",
    "$$\\pi = \\dfrac{4}{1} − \\dfrac{4}{3} + \\dfrac{4}{5} − \\dfrac{4}{7} + \\dfrac{4}{9} − \\dfrac{4}{11}…$$\n",
    "\n",
    "请注意，以上无穷级数的分子保持为4，而分母则每次递增2，并且对每一项的操作是加法和减法交替出现。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "id": "f0f0f699",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3.1415924869231824 ---->耗时: 2.113931s\n"
     ]
    }
   ],
   "source": [
    "from time import perf_counter as tic\n",
    "def calculate_pi(n_terms: int) -> float:\n",
    "    numerator: float = 4.0\n",
    "    denominator: float = 1.0\n",
    "    operation: float = 1.0\n",
    "    pi: float = 0.0\n",
    "    for _ in range(n_terms):\n",
    "        pi += operation * (numerator / denominator)\n",
    "        denominator += 2.0\n",
    "        operation *= -1.0\n",
    "    return pi\n",
    "\n",
    "start = tic()\n",
    "print(calculate_pi(6000000),\"---->耗时: {:5f}s\".format(tic() - start))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "dc5b79b2",
   "metadata": {},
   "source": [
    "### 1.5 汉诺塔\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "id": "3951614a",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[]\n",
      "[]\n",
      "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22]\n",
      "---->耗时: 4.519683s\n"
     ]
    }
   ],
   "source": [
    "from time import perf_counter as tic\n",
    "from typing import TypeVar, Generic, List\n",
    "T = TypeVar('T')\n",
    "\n",
    "class Stack(Generic[T]):\n",
    "    def __init__(self) -> None:\n",
    "        self._container: List[T] = []\n",
    "\n",
    "    def push(self, item: T) -> None:\n",
    "        self._container.append(item)\n",
    "\n",
    "    def pop(self) -> T:\n",
    "        return self._container.pop()\n",
    "\n",
    "    def __repr__(self) -> str:\n",
    "        return repr(self._container)\n",
    "    \n",
    "num_discs: int = 22\n",
    "tower_a: Stack[int] = Stack()\n",
    "tower_b: Stack[int] = Stack()\n",
    "tower_c: Stack[int] = Stack()\n",
    "for i in range(1, num_discs + 1):\n",
    "    tower_a.push(i)\n",
    "    \n",
    "def hanoi(begin: Stack[int], end: Stack[int], temp: Stack[int], n: int) -> None:\n",
    "    if n == 1:\n",
    "        end.push(begin.pop())\n",
    "    else:\n",
    "        hanoi(begin, temp, end, n - 1)\n",
    "        hanoi(begin, end, temp, 1)\n",
    "        hanoi(temp, end, begin, n - 1)\n",
    "\n",
    "start = tic()\n",
    "hanoi(tower_a, tower_c, tower_b, num_discs)\n",
    "print(tower_a)\n",
    "print(tower_b)\n",
    "print(tower_c)\n",
    "print(\"---->耗时: {:5f}s\".format(tic() - start))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "cfa15794",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.10.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
